#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/* 给定2n个整数, 从里面挑出n个整数，让选择整数的和，与剩下的整数的和的差值最小 */

vector<int> bestVec, tmpVec;
size_t min = -1, pickSum{0}, sum{}, pickNum{}, cnt{}, left{};

void fun(int *arr, int idx, int len)
{
    if (idx == len)
    {
        cnt ++;
        int remain = sum - pickSum;
        if (pickNum == len / 2 && abs(remain - pickSum) < min)
        {
            min = abs(remain - pickSum);
            bestVec = tmpVec;
        }
    }
    else
    {
        left--; // 表示处理了一个节点
        // 修剪左子树：当选择的整数的个数小于 n的时候，才执行
        if (pickNum < len / 2)
        {
            // 记录状态
            pickNum += 1;
            pickSum += arr[idx];
            tmpVec.push_back(arr[idx]);
            fun(arr, idx + 1, len);

            // 回溯状态
            pickNum -= 1;
            pickSum -= arr[idx];
            tmpVec.pop_back();
        }

        // 修剪右子树: 如果所选择的整数的个数加上未来能够选择的整数的个数大于等于 n时
        if(pickNum + left >= len / 2){
            fun(arr, idx + 1, len);
        }

        left++; // 当前i节点处理完成，从右节点回溯到父节点
    }
}

int main(int args, char *argv[])
{
    int arr[] = {12, 6, 7, 11, 16, 3, 8, 4};
    int len = sizeof(arr) / sizeof(int);
    left = len;

    for (size_t i{}; i < len; i++)
    {
        sum += arr[i];
    }

    fun(arr, 0, len);

    printf("cnt: %d elem:", cnt);
    for (int i : bestVec)
    {
        printf("%d ", i);
    }
    printf("min: %d\n", min);

    return 0;
}